% !TEX root = disc2012.tex

%\section{Applications}\label{sec:apps}
%\vspace{-0.1in}
%While the previous sections focused on performing the fundamental primitive of random walks efficiently in a dynamic network, in this section we show that these techniques actually directly help in specific applications in dynamic networks as well. 
%The following application results are specifically strong and novel for the dynamic setting, and  rely crucially on our round complexity guarantees and strong bounds in this dynamic distributed network framework. Hence previous results on random walks in static networks did not yield the following performance improvements in well-studied problems.
\vspace{-0.1in}
\section{Application: Information Dissemination (or $k$-Gossip)}
\label{sec:apps}
\vspace{-0.15in}
We present a fully distributed algorithm for the {\em $k$-gossip} problem in $d$-regular evolving graphs (for full pseudocode cf. Algorithm \ref{alg:token-dissemination}). 
Our distributed algorithm is based on the centralized algorithm of \cite{DPRS-arxiv} which consists of two phases. The first phase consists
of sending some $f$ copies (the value of the parameter $f$ will be fixed in the analysis) of each of the $k$ tokens to a set of {\em random} nodes. 
%In \cite{DPRS-arxiv}, this is implemented by a centralized algorithm assuming that the algorithm knows the entire sequence of graphs in advance. 
%Here, we show that
%this can be efficiently implemented in a distributed and localized fashion using our ``many" random walks algorithm (cf. Section \ref{sec:k-algo}) --- which shows how to efficiently perform many independent random walks simultaneously.
 %In the first phase we send some $f$ copies of each token $t$ to random nodes. 
 We use algorithm {\sc Many-Random-Walks} to efficiently do this. In the second phase we simply broadcast each token $t$ from the random places to reach all the nodes. We show that if every node having a token $t$ broadcasts it for $O(n\log n/f)$ rounds, then with high probability all the nodes will receive the token $t$.%The pseudo code (cf. Algorithm \ref{alg:token-dissemination}), analysis, and the full proof of the result (cf. Theorem \ref{thm:token-bound}) are placed in the Appendix.

 We show that our proposed $k$-gossip algorithm finishes in $\tilde{O}(n^{1/3}k^{2/3}(\tau \Phi)^{1/3})$ rounds w.h.p. 
To make sure that the algorithm terminates in $O(nk)$ rounds, 
we run the above algorithm in parallel with the trivial algorithm (which is just broadcast each of the $k$ tokens sequentially; clearly this will take $O(nk)$ rounds in total) and stops when one of the two algorithm stop. Thus the claimed bound in Theorem \ref{thm:token-bound} holds. The formal proof is below.
 
\begin{algorithm}[H]
\caption{\sc K-Information-Dissemination}
\label{alg:token-dissemination}
\textbf{Input:} An evolving graphs $\mathcal{G}: G_1, G_2, \ldots$ and $k$ token in some nodes.\\
\textbf{Output:} To disseminate $k$ tokens to all the nodes.\\

\textbf{Phase 1: (Send $n^{\frac{2}{3}} (k/\tau \Phi)^{\frac{1}{3}}$ copies of each token to random places)}
\begin{algorithmic}[1]
%\FOR{each token $t$}
\STATE  Every node holding token $t$, send $f = n^{\frac{2}{3}} (k/\tau \Phi)^{\frac{1}{3}}$ copies of each token to random nodes using algorithm {\sc Many-Random-Walks}.
%\ENDFOR

\end{algorithmic}


\textbf{Phase 2: (Broadcast each token for $O(\frac{n\log n}{f})$ rounds)}
\begin{algorithmic}[1]
\FOR{each token $t$}
\STATE  For the next $2 n\log n/f$ rounds, let all the nodes has token $t$ broadcast the token.
%\STATE When algorithm {\sc Single-Random-walk} terminates, the sampled destination outputs ID of the source $s_j$. 
\ENDFOR
\end{algorithmic}
\end{algorithm}


%\noindent \textbf{Proof of the Theorem \ref{thm:token-bound}}
%\begin{theorem}
%The algorithm~(cf. algorithm~\ref{alg:token-dissemination}) solves $k$-gossip problem with high probability\\ in $\tilde{O}(\min\{n^{1/3}k^{2/3}(\tau \Phi)^{1/3}, nk\})$ rounds. 
%\end{theorem}
%\vspace{-0.3in}
\begin{proof}[Proof of the Theorem \ref{thm:token-bound}]
%begin{theorem}
%The algorithm~(cf. algorithm~\ref{alg:token-dissemination}) solves $k$-gossip problem with high probability\\ in $\tilde{O}(\min\{n^{1/3}k^{2/3}(\tau \Phi)^{1/3}, nk\})$ rounds. 
%\end{theorem}
%\begin{proof}%[Proof of the Theorem \ref{thm:token-bound}]
We are running both the trivial and our proposed algorithm in parallel. Since the trivial algorithm finishes in $O(nk)$ rounds, therefore we concentrate here only on the round complexity of our proposed algorithm. \\
We are sending $f$ copies of each $k$ token to random nodes which means we are sampling $k f$ random nodes from uniform distribution. So using the {\sc Many-Random-Walks} algorithm, phase 1 takes $\tilde{O}(\sqrt{k f \tau \Phi})$ rounds. 

Now fix a node $v$ and a token $t$. Let $S$ be the set of nodes which has the token $t$ after phase 1. Since the token $t$ is broadcast for $2 n \log n/f$ rounds, there is a set $S_v^t$ of at least $2 n \log n/f$ nodes from which $v$ is reachable within $2 n \log n/f$ rounds. This is follows from the fact that at any round at least one uninformed node will be informed as the graph being always connected. It is now clear that if $S$ intersects $S_v^t$, $v$ will receive token $t$. The elements of the set $S$ were sampled from the vertex set through the algorithm {\sc Many-Random-Walks} which sample nodes from close to uniform distribution, not from actual uniform distribution. We can make it though very close to uniform by extending the walk length multiplied by some constant. Suppose {\sc Many-Random-Walks} algorithm samples nodes with probability $1/n \pm 1/n^2$ which means each node in $S$ is sampled with probability $1/n \pm 1/n^2$. So the probability of a single node $w \in S$ does not intersect $S^t_v$ is at most $(1 - |S^t_v|(\frac{1}{n} \pm \frac{1}{n^2})) = (1 - \frac{2n\log n}{f} \times \frac{n \pm 1}{n^2})$. Therefore the probability of any of the $f$ sampled node in $S$ does not intersect $S^t_v$ is at most $(1 - \frac{2(n \pm 1)\log n}{n f})^f \leq \frac{1}{n^{2 \pm 2/n}}$. Now using union bound we can say that every node in the network receives the token $t$ with high probability. This shows that phase~2 uses $k n\log n/f$ rounds and sends all $k$ tokens to all the nodes with high probability. Therefore the algorithm finishes in $\tilde{O}(\sqrt{k f \tau \Phi} + k n/f)$ rounds. Now choosing $f = n^{2/3} (k/\tau \Phi)^{1/3}$ gives the bound as $\tilde{O}(n^{1/3} k^{2/3} (\tau \Phi)^{1/3})$. Hence, the $k$-gossip problem solves with high probability in $\tilde{O}(\min\{n^{1/3}k^{2/3}(\tau \Phi)^{1/3}, nk\})$ rounds. 
\qed
\end{proof}
\vspace{-0.1in}
Note that the mixing time $\tau$ of a regular dynamic graph is at most $O(n^2)$ (cf. Theorem~\ref{thm:mixtime}). Putting this in Theorem  \ref{thm:token-bound}, yields a better  bound for $k$-gossip problem in a regular dynamic graph.

\iffalse
%**Note: I think a more careful analysis of lemma~\ref{lem:node-counting} improves the round complexity by a factor of $d$ since we consider $d$-regular graphs. 
%\vspace{-0.05in}
\subsection{Decentralized Estimation of Mixing Time}
\label{sec:mixest}
\vspace{-0.05in}
We placed this full section in Appendix (cf. Section \ref{application mixing time}) due to lack of space.  

We focus on estimating the {\em dynamic mixing time} $\tau$ of a $d$-regular connected non-bipartite evolving graph $\mathcal{G}$. We discussed in Section \ref{mixing_time} that $\tau$ is maximum of the mixing time of any graph in $\{G_t : t \geq 1 \}$. To make it appropriate for our algorithm, we will assume that all graphs $G_t$ in the graph process $\mathcal{G}$ have the same mixing time $\tau_{mix}$. Then $\tau = \tau_{mix}$. %While the definition of $\tau$ (cf. Definition \ref{def:mix-dynamic}) itself is consistent, estimating this value becomes significantly harder in the dynamic context. Therefore we need careful analysis and new ideas to obtain the results. 
We present an algorithm to estimate $\tau$. The main idea behind this approach is, given a source node, to run many random walks of some length $\ell$ using the approach described in the previous section, and use these to estimate the distribution induced by the $\ell$-length random walk. We then compare the  distribution at length $\ell$, with the stationary distribution to determine if they are {\em close}, and if not, double $\ell$ and retry. The algorithms and related results are placed in Appendix (cf. Section \ref{application mixing time}).  
\fi
%\begin{theorem}
%Given a node transitive evolving graphs with dynamic diameter $D$, a node $x$ can find, in $\tilde O(n^{1/2} + n^{1/4} \sqrt{D\tau(\epsilon)})$ rounds, a time $\tilde \tau_{mix}$ where $\epsilon = \frac{1}{6912e\sqrt{n} \log n}$. (Shall write it carefully)
%\end{theorem} 



